home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 12713 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.8 KB
  1. Path: hubcap.clemson.edu!hubcap!mjs
  2. From: mjs@hubcap.clemson.edu (M. J. Saltzman)
  3. Newsgroups: comp.lang.c,comp.lang.c++
  4. Subject: Re: Statistically Random Number algorithm
  5. Date: 18 Mar 96 23:00:32 GMT
  6. Organization: Clemson University
  7. Message-ID: <mjs.827190032@hubcap>
  8. References: <314D0B67.3C16@psu.edu> <4ikle5$1rf@sparcserver.lrz-muenchen.de>
  9. NNTP-Posting-Host: hubcap.clemson.edu
  10. X-Newsreader: NN version 6.5.0 #1
  11.  
  12. watzka@stat.uni-muenchen.de (Kurt Watzka) writes:
  13.  
  14. >"Jason A. Soloff" <jas251@psu.edu> writes:
  15.  
  16. >>I am working on a monte carlo simulation program to model some problems 
  17. >>in astronomy.  One thing I am running into, however, is the problem of 
  18. >>the pseudo-random number tables.  Does anyone have an algorithm (or 
  19. >>code) for a truly statistically random number generator?
  20.  
  21. >A guy from NASA once suggested that it is really simple. All you need
  22. >is a satelite that records the background radiation. You digitize 
  23. >that and have a perfectly random sequence of random numbers.
  24.  
  25. In a seminar that I saw, Percy Diaconis (the Harvard
  26. mathematician/magician known for some results about card shuffling)
  27. pointed out that some experiments with using atomic particle decay to
  28. produce random bits produced notoriously bad results, based on even
  29. simple tests for randomness.
  30.  
  31. >For us mere mortals, the quote from John v. Neumann still holds:
  32.  
  33. >   Anyone who considers arithmetical methods of producing
  34. >   random digits is, of course, in a state of sin.
  35.  
  36. >So, the answer for C (and C++) still is: Use rand(). If rand() is not
  37. >good enough for you, maybe the random number generators available
  38. >on your system will be a solution.
  39.  
  40. If you are serious about generating random numbers, the rand()
  41. facility on many systems will not be suitable.  The drand48 facility
  42. available on many Unix systems is better.  Numerical Recipes actaully
  43. has a fairly decent one (according to Diaconis).  And there are
  44. others--some generators and test codes are available from
  45. Netlib (http://www.netlib.org), for instance.
  46.  
  47. >The word algorithm implies a _deterministic_ process, and there
  48. >cannot be a deterministic process that produces _random_ output.
  49.  
  50. Actually, there is a whole field of _randomized algorithms_.  One can
  51. design algorithms that make random choices at certain points, and
  52. analyse their probabilistic complexity and/or liklihood of success.
  53. For example, randomized algorithms might run much faster than
  54. deterministic ones, but with some probability of failure.  One might
  55. run such an algorithm several times to reduce the failure probability
  56. to something negligible, and still save time over a deterministic
  57. method.
  58.  
  59. Of course, the random component is an *input* to such an algorithm,
  60. not an output.  If one wanted to *implement* a randomized algorithm
  61. (and get the predicted behavior) one would need a good random number
  62. generator...
  63. -- 
  64.         Matthew Saltzman
  65.         Clemson University Math Sciences
  66.         mjs@clemson.edu
  67.